/* 
 * Binary Tree Postorder Traversal
 */

#include "../../func.h"

vector<int> postorderTarversal(TreeNode *root)
{
    vector<int> result;
    stack<TreeNode *> s;
    TreeNode *p = root, *q = nullptr;

    do
    {
        while (p != nullptr)
        {
            s.push(p);
            p = p->left;
        }
        q = nullptr;
        while (!s.empty())
        {
            p = s.top();
            s.pop();
            if (p->right == nullptr || p->right == q)
            {
                result.push_back(p->val);
                q = p;
            }
            else
            {
                s.push(p);
                p = p->right;
                break;
            }
        }
    } while (!s.empty());
    return result;
}

//Morris todo